package algo.graph;

import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;

public class BreadthFirstPath extends Path {

	public BreadthFirstPath(Graph g, int s) {
		super(g, s);
		marked = new boolean[g.vertexCount()];
		precedents = new int[g.vertexCount()];
		marked[s] = true;
		queue.add(s);
		bfs(s);
	}

	private void bfs(int s) {
		while (!queue.isEmpty()) {
			int first = queue.remove();
			for (int neighbor : g.adj(first)) {
				if (!marked(neighbor)) {
					queue.add(neighbor);
					marked[neighbor] = true;
					precedents[neighbor] = first;
				}
			}
		}
	}

	private Queue<Integer> queue = new ConcurrentLinkedQueue<Integer>();
	private boolean marked[];

	@Override
	protected boolean marked(int v) {
		return marked[v];
	}


}
